package com.ry.day1129;

import java.util.ArrayList;
import java.util.List;

public class LC1205 {

    static class Solution {
        /**
         * @param matrix: a 2D array
         * @return: return a list of integers
         */
        public int[] findDiagonalOrder(int[][] matrix) {
            int n = matrix.length;
            int m = matrix[0].length;

            int all = n*m;
            int[] ans = new int[all];
            //up: true 从下往上走  反之从上往下走
            boolean up = true;

            int idx =0;

            for (int i = 0; i <n ; i++) {
                //x,y  对角线左下角的起点
                int x = i;
                int y =0;

                List<Integer> data = new ArrayList<>();
                while (x>=0 && y<m){
                    int value = matrix[x][y];
                    data.add(value);
                    x--;
                    y++;
                }

                if(up){
                    for (int j = 0; j <data.size() ; j++) {
                        ans[idx++]= data.get(j);
                    }
                    up= false;
                }else{
                    for (int j = data.size()-1; j >=0 ; j--) {
                        ans[idx++]= data.get(j);
                    }
                    up= true;
                }
            }


            for (int i = 1; i <m ; i++) {
                //x,y  对角线左下角的起点
                int x = n-1;
                int y = i;

                List<Integer> data = new ArrayList<>();
                while (x>=0 && y<m){
                    int value = matrix[x][y];
                    data.add(value);
                    x--;
                    y++;
                }

                if(up){
                    for (int j = 0; j <data.size() ; j++) {
                        ans[idx++]= data.get(j);
                    }
                    up= false;
                }else{
                    for (int j = data.size()-1; j >=0 ; j--) {
                        ans[idx++]= data.get(j);
                    }
                    up= true;
                }
            }

            return ans;
        }
    }


    public static void main(String[] args) {
       int[][] arr = {
               {1,2,3},
               {4,5,6},
               {7,8,9}
       };
        Solution obj = new Solution();
        int[] data = obj.findDiagonalOrder(arr2);
        for (int datum : data) {
            System.out.print(datum+" " );
        }

        System.out.println();

    }

    static int[][] arr2 = {
            {303,4221,56,2024,-30851},
            {300,3708,-53,-2307,599},
            {45,1915,276,1703,28184},
            {507,2173,-104,-1558,-13119},
            {142,654,-308,3107,-5402},
            {93,5272,-30,876,-20062},
            {19,255,-209,-1519,-43417},
            {37,5344,51,-3187,-23857},
            {336,855,-274,2003,26800},
            {222,3622,207,2,-37644},
            {385,5062,85,280,-33387},
            {319,3598,-121,2736,42548},
            {166,883,-1,1996,-19937},
            {525,863,20,2845,-19528},
            {203,1318,111,-372,34026},
            {304,2232,-12,-2288,-13688},
            {253,1829,-185,1670,29202},
            {338,5512,8,3037,-3562},
            {490,3215,29,3830,-24791},
            {77,4281,-91,-1065,3291},
            {501,3848,24,-2034,-24271},
            {343,5168,156,819,-4476},
            {426,4333,310,-298,35687},
            {459,2163,341,103,-14538},
           // {37,1184,332,-2479,-4195},{515,1294,137,-2065,-23408},{361,4963,-395,-1529,-32446},{17,3343,-197,-1638,-13281},{274,5496,304,537,-29776},{476,3605,-238,2756,-9891},{15,5110,134,-140,34219},{4,2123,-34,1068,-30096},{461,1580,26,569,-31642},{386,1298,37,-46,7106},{95,1482,4,4884,-34269},{289,2106,21,3439,40355},{105,3846,-47,-1726,-8480},{505,4452,214,-2761,3346},{175,4177,191,-1142,18932},{451,1076,-95,-2023,21886},{200,4833,295,-3579,16640},{146,2264,-64,2365,-20724},{318,4636,-120,-3669,12307},{77,2504,62,-1583,-12914},{0,3329,-38,-209,-17835},{22,66,214,-1435,19568},{320,5179,86,-2024,5055},{128,1948,49,-674,5747},{63,4771,234,644,15331},{317,2709,-219,-615,45294},{396,3643,-19,-1642,48210},{72,2838,-92,-3361,-30536},{126,1604,-85,-3239,49045},{248,2141,88,-436,-7228},{189,3101,214,-830,-11660},{151,682,-288,1082,-6919},{274,1985,-285,3060,19022},{486,2560,459,-1327,3996},{409,4488,-295,-1163,-31799},{191,5157,-72,215,-44144},{147,2018,-78,1647,8379},{373,2870,-158,-1711,-2968},{178,4833,216,-2328,8423},{234,3734,-134,-3313,-40353},{303,4757,88,4212,-42087},{300,4777,146,109,-10282},{254,2758,216,1009,-820},{240,1846,420,1322,11457},{453,2180,-289,-3072,37038},{198,1418,507,374,18118},{226,1063,414,2223,2262},{17,4252,-433,4081,-36872},{177,1428,-245,3198,8172},{25,1884,52,151,21169},{496,872,-5,638,-31939},{293,761,-2,357,20392},{384,2471,49,-2294,-3467},{397,2454,64,-1927,16962},{329,3360,-326,492,37782},{151,2661,11,-936,-13405},{137,87,-184,-1783,-20590},{37,3302,-107,1120,12926},{194,4467,119,4731,-8164},{307,989,165,-3550,-6064},{346,1248,175,-2104,4330},{36,5226,8,-1770,24394},{271,4614,142,2360,-13267},{143,4698,-185,-1251,24869},{441,1510,17,2164,15072},{94,1940,2,1507,4540},{201,1589,148,-301,-15094},{337,4072,-225,-2849,13854},{73,28,38,-1260,-32395},{6,4215,107,2028,40384},{263,5306,226,-319,15874},{254,4308,-387,2978,-38070},{390,313,44,3854,21828},{440,2888,-420,3736,13365},{258,5180,-109,1010,22925},{149,2293,-162,-3007,5650},{127,1690,-274,-1524,-2935},{128,4377,213,1944,15126},{498,944,239,259,28556},{54,2028,73,-3094,-993},{157,804,114,-439,20588},{155,3217,388,-2519,27459},{496,1840,138,-810,37053},{113,3819,56,-276,-11521},{321,3562,347,2307,28041},{443,2774,17,-3243,-20022},{65,281,-167,2941,35490},{0,3842,-74,651,-8569},{11,2494,-325,2949,-28002},{516,3314,-187,-1254,-4697},{405,1898,501,849,21907},{112,4033,235,610,15607},{133,1085,116,-730,5038},{147,2746,-282,-4289,1864},{388,3383,19,3230,22995},{285,3171,-278,-2099,-18477},{151,2347,29,-2653,6468},{446,2030,10,185,27895},{356,4994,77,1886,13282},{502,5287,281,4050,-23454},{5,3450,-345,1732,-8185},{197,3126,-397,468,23504},{448,3875,-326,1348,44047},{280,4427,-154,509,1293},{413,996,400,1289,-833},{114,3216,77,-2975,44565},{64,2508,59,434,-12854},{376,3669,-204,3566,2912},{414,4190,24,1908,30597},{467,2559,277,2733,41574},{429,2090,-220,-1024,43076},{300,1951,68,4353,28647},{462,4448,292,929,12271},{463,1472,351,3496,-1152},{414,3853,66,1679,-11587},{225,396,-62,2421,1693},{336,1078,158,-4393,25956},{118,2153,57,345,10807},{505,1743,308,2802,4653},{512,4830,-401,1008,-4378},{410,2829,-224,-1621,25061},{140,610,-183,307,-4355},{223,1177,-11,-4188,-324},{465,648,106,-3603,31056},{378,5487,187,-309,7735},{5,3332,323,-2229,-4326},{233,1601,470,-1285,21458},{490,4469,377,-579,45666},{452,1340,-63,1295,16779},{513,3946,-92,109,15548},{485,1987,-188,4032,-14868},{52,2684,30,-1596,-23923},{183,821,318,151,-14356},{68,3766,-203,1113,37660},{270,2503,-116,-914,79},{298,4144,53,1996,-21408},{208,240,-168,2312,-12233},{210,5504,266,229,8665},{421,3043,287,-676,-9931},{185,5176,63,977,-13714},{239,1287,168,3502,2254},{441,5190,78,-939,-845},{401,248,198,4738,1541},{192,2618,-200,-507,44361},{265,1263,221,1577,11708},{398,3433,444,3410,-2808},{378,1130,-18,1164,-24967},{37,2534,14,-1859,3173},{253,5174,33,2951,-28938},{7,4914,-5,4008,-17731},{357,5012,456,1044,-3206},{124,53,355,1309,32300},{104,4362,431,2332,21468},{14,294,-135,-3016,-1924},{323,3260,-180,155,6462},{453,1160,36,2186,-39323},{352,4598,196,-1368,15906},{341,2968,54,1620,23221},{367,1326,39,1345,-26788},{307,1854,162,1127,-3440},{210,5212,-207,-562,2435},{83,4389,72,959,4049},{78,241,66,-1593,-2166},{425,4008,-103,-2411,-27891},{53,3505,-51,1284,-3978},{301,5046,48,-407,23456},{464,632,-42,2761,21156},{258,1888,19,-2107,-29958},{42,5121,123,-893,18509},{5,301,-310,-2639,-8412},{241,3421,-99,1837,11833},{498,460,-117,-844,11828},{126,1589,-114,994,7855},{234,4015,-33,2192,41100},{63,271,258,4664,2655},{13,3148,48,-2984,-30859},{159,3806,203,2602,-6031},{335,3665,-375,2438,44107},{366,3599,16,-1450,-48626},{128,2,1,-1354,-36138},{205,1172,-316,-1750,27142},{142,3918,105,-1321,-13210},{360,3635,-92,-1237,34680},{461,975,351,1325,10218},{220,1303,97,-1558,35379},{248,2830,31,2264,-13647},{136,1752,-368,-2317,14159},{8,3461,-229,-2292,-8309},{60,5523,161,936,-2582},{112,4789,-49,2882,2984},{200,2297,-266,-765,-35095},{374,2442,389,840,8727},{120,3547,194,-4360,-43957},{487,966,-298,-2095,-2008},{244,2182,-141,4371,19653},{211,156,-338,-2427,26591},{7,1675,-95,131,-27943},{104,1930,23,3588,22972},{108,2889,-51,-560,49733},{357,5360,333,1293,19926},{192,3109,72,-2236,9453},{63,2104,173,-3465,196},{129,4357,-6,-3426,-629},{362,1019,-186,1289,14153},{355,4996,-55,-993,-37542},{41,4427,-208,-467,-6934},{278,3797,-64,-1247,-274},{425,1423,191,927,22994},{431,574,11,3288,8405},{109,984,-5,-287,-6493},{47,4568,-428,4085,-23904},{206,4522,-314,284,-25965},{477,4753,153,-341,23441},{199,1288,116,780,-15726},{193,3139,215,649,-25445},{264,1013,-74,-2084,-27207},{66,1051,381,556,25412},{89,3618,71,-3112,44591},{191,4369,-14,22,-16603},{457,1357,144,3305,-10026},{433,790,142,2083,-5254},{38,4773,230,293,17982},{369,3143,180,519,12349},{340,3726,-207,801,36405},{517,382,74,-1937,-25914},{187,4282,-16,-1936,-25142},{170,998,221,3767,9853},{453,4633,105,-3478,11016},{333,3377,-169,-273,-7202},{58,2518,142,-3580,25891},{146,2005,-233,-2038,7558},{166,202,11,3116,-12046},{475,4377,-71,-3031,-34008},{467,1275,286,3314,8670},{378,3800,87,215,17533},{352,3214,66,-1976,-11896},{86,4030,215,-516,-9921},{199,2948,24,-939,-30722},{45,2357,-387,-1769,9069},{415,2879,-28,3239,-5643},{437,2830,279,1744,14752},{63,5004,-257,2669,-5930},{244,943,-186,-1616,-2750},{508,658,-373,931,-29213},{331,191,-486,297,33735},{191,579,363,-2108,21507},{243,5035,432,919,1725},{304,3264,-6,-1583,28559},{344,1730,-248,2888,43436},{473,2441,287,1007,18214},{195,2323,-303,-2432,22285},{83,898,-201,2982,-202},{237,340,232,-2078,-15572},{471,4777,274,912,-11721},{356,4181,-9,-2549,13329},{495,4682,320,-4850,17263},{241,1198,-158,1022,-30696},{379,1038,-463,-1201,-3262},{399,5281,226,-3623,-15753},{285,3428,-145,-576,31613},{128,2448,-97,754,-10293},{24,3644,-55,2935,18850},{332,356,40,-221,-30700},{184,3225,118,-174,15354},{155,2139,-23,-125,-2938},{77,1580,-233,1014,-5743},{41,3221,-389,1936,13711},{238,5482,-160,2982,-35447},{148,4121,-41,2919,-6238},{497,3325,-39,-1802,25124},{83,3456,-16,198,-7585},{125,243,278,1345,-265},{497,4559,3,1824,-40487},{437,4273,102,1765,-20252},{513,4205,-141,58,-32659},{129,2946,-206,-257,-25547},{463,2362,-358,-2227,-11996},{402,3315,307,945,35097},{427,4526,-434,-1893,-11645},{106,4927,16,136,-3368},{457,4908,181,1982,-12606},{455,2333,346,-2122,28298},{148,3271,47,31,-11343},{307,120,-257,-875,-28169},{392,694,-212,855,14348},{343,475,-54,-2215,32368},{429,4620,103,950,-11039},{166,2670,289,-1786,-8972},{374,5299,34,-550,14218},{330,2427,14,2195,-5435},{196,1928,147,-328,8469},{484,402,117,4473,49316},{475,3614,-148,-2156,22202},{261,3930,11,574,21057},{495,3499,-234,-828,20537},{467,82,-376,32,-12826},{209,3931,43,-97,-22975},{127,4144,-240,-1823,12175},{245,4117,-26,271,38505},{22,2474,269,208,-4311},{292,2988,187,-2059,-2760},{268,4568,-251,-4465,-16501},{190,5147,219,-4908,10668},{73,5467,238,-1978,14164},{372,3802,53,465,30229},{408,3084,-80,4205,15038},{42,3292,155,1543,23371},{496,2636,325,1015,-39320},{360,2549,43,3044,19715},{353,5123,-260,2600,-9704},{73,4588,-144,-1551,7513},{206,3994,-281,147,17808},{270,4737,-168,1835,1311},{236,352,-213,3749,-18392},{273,1666,-236,1988,1173},{417,2950,17,-1534,37029},{317,222,37,-2277,2752},{74,818,-45,1971,20409},{93,5204,-70,-4919,6821},{214,4071,-135,-4347,28686},{301,3554,104,-1475,-4123},{363,1155,75,2575,-25614},{172,3702,-133,2931,23666},{481,2226,68,-3324,-18875},{456,347,21,-1491,-26597},{418,2716,-41,-3802,25513},{194,2334,-77,-2734,22609},{65,3155,-327,2620,11281},{372,2345,50,-1153,32481},{99,76,-87,-2839,17315},{470,600,-340,-902,20095},{283,3111,-116,4041,-2174},{149,2335,159,-329,4769},{76,1061,33,1662,22151},{24,855,-235,4103,7601},{79,2226,-245,0,-32427},{104,1151,208,-555,36157},{64,1558,-14,988,-3123},{74,3731,-24,1299,2664},{268,74,-20,-1316,11741},{490,2971,405,-3888,17721},{422,2898,309,1985,21885},{379,1886,-235,-2711,31420},{376,2468,-254,-4067,21950},{487,5002,88,-68,-6550},{99,5055,-129,430,27000},{293,3210,406,1000,-2015},{322,2752,104,903,25279},{384,284,-148,-1024,17046},{415,2605,119,2174,23777},{432,4281,439,-84,3547},{96,1899,-175,-244,-11958},{66,2065,54,-3466,-376},{285,2538,321,-4965,4086},{513,1495,-87,-4635,5159},{120,5460,132,1912,-1412},{151,5342,242,3160,-11777},{299,4105,-92,-196,-6618},{223,4337,-257,-1721,-10630},{266,4330,418,1119,-4176},{195,4364,254,972,-31623},{140,5319,-53,-2032,21665},{459,526,-95,1146,9095},{24,155,-389,-1403,5748},{241,5139,287,-356,1177},{510,4531,348,-2591,-19618},{246,1004,-215,-3116,-3432},{324,4460,205,-3965,-17854},{158,3911,217,1577,7186},{135,2155,82,-1680,-18349},{216,2356,121,1107,-31641},{402,1683,-444,4350,4695},{139,4829,-196,464,3535},{354,2305,-140,3889,-8734},{51,308,-104,161,14660},{244,4373,175,-848,-18409},{524,4848,-352,484,-1220},{421,1055,66,-1508,-6561},{382,928,-292,198,9184},{120,191,-308,1028,9283},{375,1211,-124,3874,26123},{26,2068,-89,992,-45937},{387,4676,-52,1982,2799},{524,5485,-4,-1656,-24920},{421,3489,353,-3933,-6984},{75,5080,233,-2614,2590},{181,5467,46,-720,-7465},{447,4860,-306,3072,2887},{89,2101,-195,1704,42260},{197,597,195,-1185,-45355},{105,3894,-142,-3893,-3384},{143,2546,99,-4964,1715},{403,706,422,-3229,-36254},{169,2115,-443,915,20584},{333,3484,-222,-4018,-21482},{480,1560,201,-31,22401},{290,4865,49,1136,-799},{478,1521,298,-4268,4236},{50,5423,-114,818,-9364},{369,2112,-197,391,-16346},{184,3852,-86,-2707,-6814},{59,4761,-148,873,-36375},{352,71,-78,464,-18797},{211,1085,-110,-4767,39907},{272,4386,-1,897,-16441},{508,4123,90,-1260,-18325},{187,2102,-25,358,-15341},{231,1625,-74,125,-19068},{397,4522,93,356,8556},{357,255,-165,1063,31769},{308,5498,-35,643,1299},{41,1618,-139,-908,12189},{139,118,85,3141,15902},{401,1613,168,747,-26766},{322,4561,-388,-89,-13429},{324,2895,-289,-646,6587},{122,263,-458,580,-8101},{338,3810,150,-4516,12330},{394,2789,-235,487,20603},{109,1187,315,-3245,-32127},{146,4535,242,-1702,32663},{175,2701,-239,550,28312},{185,106,96,175,-15136},{121,4816,302,-1134,-22221},{115,251,69,631,14222},{200,4844,-466,-2922,-8671},{467,1295,-211,1164,3490},{281,4987,-304,-3253,-11222},{0,1917,106,1011,-29044},{133,4572,185,180,15997},{354,1947,340,-3672,10404},{147,4343,-129,-711,-11128},{134,2176,317,-3802,1641},{188,3531,232,512,15635},{515,2850,51,-35,-42203},{259,5424,380,-4193,-26003},{15,4178,38,608,-7438},{427,4428,-316,3725,363},{237,1348,419,2547,22028},{99,3740,-263,-5205,-7005},{421,1863,116,-2129,-22315},{24,3702,231,3754,21433},{240,2424,128,-3551,13583},{501,4724,-154,-1080,-23998},{510,4867,-184,1184,15489},{514,3494,-134,-1842,11240},{448,1438,332,731,9520},{513,3765,230,-3257,-42521},{92,1383,196,1999,-5263},{133,2185,180,2386,-11737},{513,5242,412,552,35955},{305,1180,-135,-1168,-21697},{72,5060,-11,2015,-9616},{6,3534,130,-1723,-2029},{100,1881,-67,-2223,13549},{489,3693,-227,2230,-45511},{373,1212,9,-761,17337},{285,1098,41,-2118,7534},{248,4392,-1,-1615,9541},{129,3837,222,-2195,-717},{402,197,-54,2097,-251},{482,3802,-330,2390,-3516},{111,5080,-228,-1364,-21551},{432,1772,-2,757,-25360},{231,5116,-42,2735,-6833},{27,1822,31,-2956,23000},{368,3709,-256,-1542,22499},{411,1606,-181,-884,8466},{0,4708,-81,1207,8280},{262,5202,152,930,26073},{116,999,42,3367,-4391},{283,2391,349,-3363,-10916},{505,405,-124,-3019,-9824},{258,5273,-47,2486,13114},{220,2366,-132,3251,25714},{345,4662,188,-621,990},{279,3746,134,-3458,12793},{312,4933,-213,-548,17987},{358,251,-64,-1223,11132},{466,1355,88,1505,-26348},{93,151,-73,1176,-26099},{34,4517,-147,3559,21089},{303,1750,98,-4,-32166},{397,2163,-315,4184,-20672},{168,1072,18,-1817,18520},{382,1889,-345,-928,3866},{277,4882,-221,-3747,1215},{4,3030,-207,1068,-13176},{364,3603,278,-455,23174},{143,3664,-88,2421,5430},{502,5495,-260,-1957,5492},{389,1868,-144,2096,32628},{491,5137,255,-4459,269},{109,4212,-428,2803,-4415},{105,4929,154,3943,6446},{138,5184,250,-4476,-29816},{472,2190,80,4351,-2395},{428,468,163,3674,17588},{408,1519,-129,1945,5030},{41,5450,-15,-2042,28825},{95,3889,115,-3123,45707},{394,5287,-173,-3616,3425},{115,3465,412,2751,-46329},{314,5432,-57,19,28047},{263,535,28,-3435,-34286},{422,2320,247,467,-12634},{406,1312,19,5195,3319},{355,2386,-310,2828,-39903},{264,3616,21,-756,621},{389,4072,318,-1051,22847},{106,5446,112,-271,-39722},{43,2304,-25,3319,-21948},{198,4915,93,2168,17083},{98,3879,14,-2008,29307},{74,2723,6,466,166},{514,4380,56,4503,39482},{168,1964,-392,-1569,27818},{464,5451,114,-2333,41757},{341,2528,84,-1062,33693},{302,1116,-12,1083,13228},{61,2450,49,-2990,30519},{221,2311,225,-1789,10083},{327,4799,328,19,-9774},{243,1874,174,-2590,2908},{111,4092,26,-1865,1429},{155,2468,-438,392,-18227},{442,3474,-174,227,8465},{395,2302,-146,892,37878},{149,3359,-209,-1454,-10610},{314,343,-295,370,27328},{508,551,-229,-1455,-25099},{119,5305,-176,-921,10926},{323,3068,27,-197,48834},{13,3181,-357,-2970,29588},{374,687,365,-4252,34843},{504,5501,-93,3333,30787},{511,836,47,641,-8017},{389,672,-36,2216,-32595},{215,5113,-6,-5369,-4070},{107,4342,-355,-2981,-706},{425,681,-124,-571,32115},{117,4314,-168,795,25963},{269,3261,-13,-3659,-7295},{345,44,378,2403,-3712},{340,2240,-111,-288,-42134},{515,801,-95,602,12495},{78,3093,-357,767,-7634},{441,4158,-193,-627,3815},{268,4381,195,-421,2461},{196,5356,-120,-247,10072},{401,2632,46,-3355,-32539},{188,2961,-32,-1708,5365},{477,4949,-34,-1415,39139},{367,5505,320,-3185,-40088},{239,2640,-336,-2869,25935},{86,3002,-242,263,22342},{216,3417,-108,-2201,31070},{390,1063,-217,1630,14553},{263,3968,-38,-2841,39210},{462,3663,-34,-836,6059},{119,2672,131,-1598,40945},{163,2710,227,2668,-11544},{87,2856,-332,-3198,-12623},{38,4271,-245,398,23350},{110,4823,329,428,22875},{475,4878,246,1273,2101},{513,2082,-489,2202,9226},{136,2409,-98,-465,-30596},{240,2012,28,-557,37096},{44,1741,-69,1147,29771},{57,4225,312,761,-39212},{70,437,-369,-558,-30543},{86,1701,-356,675,-26177},{10,1611,194,-3555,-9054},{69,3234,358,-1650,-3982},{455,2121,-289,-358,23334},{479,4452,69,3415,23807},{368,4924,-109,39,-22748},{369,1546,-98,-2157,-25099},{93,3575,-342,4018,-23246},{237,5373,-149,-797,11308},{42,1921,29,2118,-6027},{280,4295,-74,-1100,6367},{280,4703,60,-966,-8168},{74,1763,-234,659,-3015},{152,2983,-294,-99,-16745},{325,2548,54,-2179,17335},{66,2688,339,230,24822},{23,2870,-12,2734,-23626},{57,4182,-98,2870,-13791},{91,2582,-87,-2460,13464},{447,5116,141,2030,-35135},{384,321,391,-3379,4576},{50,380,-250,-4480,40656},{479,1153,-79,162,-21967},{362,1646,105,-323,-45108},{331,3834,101,3712,25151},{274,247,-35,-2310,-30784},{276,5063,66,-1520,20141},{292,5111,292,1458,5531},{268,98,162,807,11161},{229,2413,402,-2509,-172},{71,2911,-215,-763,8372},{226,2461,-85,2177,-45751},{314,4331,-219,-721,-4043},{75,539,29,1816,-2487},{521,4399,-87,-2899,98},{151,1596,277,-1596,-10688},{313,3537,-360,1939,37939},{356,4338,92,-2653,-36644},{146,3927,55,-3883,16950},{485,2974,386,-1141,-10207},{141,1636,-414,-990,-42882},{409,1004,26,-614,-4316},{184,3818,226,-2630,7334},{420,4184,-265,-1554,8754},{301,1873,159,-2023,-6475},{83,4517,-73,978,26969},{444,1218,365,1131,13409},{213,873,-274,-2346,-186},{493,4288,-146,611,4431},{513,3601,-77,1890,8440},{207,3620,12,-2912,-8648},{249,5046,299,795,-17267},{37,1080,-249,-2882,3091},{143,5331,51,1317,-23308},{233,1247,-272,-2864,-32138},{165,3071,266,696,21803},{11,1925,245,-3641,-9126},{496,3740,38,279,-18191},{195,2757,395,3121,-21777},{524,4707,-267,2264,22365},{267,2311,445,3302,-11142},{335,452,-321,-707,-17020},{200,4483,-129,-3886,20401},{16,36,-384,-3713,22502},{76,2806,286,-3273,13472},{252,3954,-195,3374,-9615},{364,4914,248,-3243,-25187},{520,1033,-207,2939,26613},{162,2847,-251,-446,-16308},{263,5298,-51,-2267,-13251},{74,4323,-30,1306,-11100},{113,4930,125,-650,26717},{442,419,-188,-3014,-30318},{108,1103,95,1231,-9892},{519,4438,58,2125,10584},{416,4442,-211,2088,-4618},{297,3751,-92,-1345,39379},{281,3533,-182,-364,835},{356,4721,204,-3151,9116},{313,870,76,-406,25553},{250,2998,-54,956,5225},{171,2136,264,-351,-42025},{275,3490,-164,1956,3359},{35,550,44,-1440,-6503},{3,3781,-85,1512,-22687},{91,2705,-369,43,-28492},{223,2816,162,-3127,29866},{393,2967,35,-765,-3917},{93,1674,-48,-2549,3354},{183,4554,40,-1371,-5019},{20,4231,-400,-1027,-5686},{86,3895,71,822,31981},{48,3851,-42,-2628,8527},{144,4799,112,-889,34531},{265,1089,-7,-815,-5285},{87,5150,337,-1310,17312},{206,1739,-314,276,-15565},{379,1528,-143,-2865,43852},{431,5234,271,2903,26118},{471,3730,-221,-1981,-304},{412,4639,362,4198,-18957},{521,2775,224,3924,21216},{417,2583,-157,4754,-7514},{320,5410,468,3624,24902},{40,3689,405,-190,-4877},{375,1092,392,510,20944},{496,2047,210,3986,23290},{255,5161,80,-3306,-11903},{267,3713,251,-2320,-4412},{521,2695,-327,2178,11256},{180,3305,85,-3218,-18564},{149,4271,169,4487,-2048},{369,3372,-7,3182,-16078},{63,3995,244,3956,7016},{46,3030,227,2152,-8482},{49,5123,-136,-387,-2410},{499,3927,213,17,25006},{258,3967,61,-2629,26127},{263,1027,22,-3123,-2300},{237,3014,376,-844,1661},{406,5090,-38,-4178,-5761},{512,2663,65,1647,-2535},{194,4853,-47,418,-23473},{316,1141,-448,-1068,-1114},{32,3728,-327,-1151,-7529},{13,833,63,2017,25647},{46,2582,-113,3301,-5460},{417,1970,69,-938,9299},{386,4206,149,-876,-9785},{491,1067,376,2902,-22929},{483,5255,257,-3706,1552},{485,3692,150,-163,15691},{237,4930,-22,742,-28972},{253,2880,-361,2468,16023},{32,3163,-308,-1313,-3330},{150,986,-292,1858,12923},{512,3821,-46,2804,-36652},{190,1993,-23,1841,22869},{95,4801,304,-3323,40435},{291,141,80,-5326,12297},{391,3395,-230,-2390,26664},{368,5227,-295,-654,-48081},{339,3584,-198,3151,-11046},{24,863,60,4933,-28005},{0,1453,135,-865,11795},{509,1992,249,-4443,-1438},{154,2762,14,3372,17204},{14,4485,-369,1317,37891},{334,76,216,3015,8774},{165,4949,7,1688,-34607},{234,4905,280,5212,9317},{59,4916,-134,1033,-3158},{315,4127,-79,-1660,-38839},{517,3098,508,5319,14257},{220,1873,43,1391,5654},{70,691,64,-899,10691},{474,2895,-103,1750,24987},{228,112,-179,3953,25991},{426,4828,276,-21,23604},{53,4233,176,3535,20868},{80,4800,-83,3507,3153},{339,3954,-131,-759,-25199},{139,4734,-176,-1407,27123},{7,875,-221,1762,-2949},{218,3071,-13,1279,-19522},{361,4037,54,-954,-182},{217,2744,-61,1592,23460},{293,4551,59,2726,-23058},{278,2775,96,437,-7919},{186,3552,124,3695,20067},{450,3156,19,-3527,-11710},{116,2900,-455,-2175,-4491},{334,299,84,1912,22437},{473,3109,-261,-503,1658},{494,5187,-252,535,-3230},{369,3430,-248,-1375,-27826},{408,4784,175,2142,24824},{3,3875,-22,2347,-4600},{170,2087,122,80,-21659},{310,157,168,74,-8844},{245,1059,74,283,-3714},{157,407,193,-22,16533},{149,4460,-48,-1867,-25357},{87,3505,222,-3744,9016},{142,3831,-244,-1084,-34954},{403,4777,-136,1361,25593},{72,2399,108,614,39913},{501,1985,12,-743,-3581},{426,1822,-292,-5166,-25479},{510,5223,437,3310,-6616},{138,1883,-118,-1228,-10886},{506,2722,-348,985,23927},{163,3754,308,587,15881},{86,5212,198,-4066,-7533},{353,4423,-222,-1929,5099},{464,1702,65,228,13164},{123,2918,296,435,-4221},{10,416,-101,84,-8789},{186,4933,88,1055,24260},{393,4640,-282,-309,34711},{507,356,82,-1140,-34314},{377,3535,26,1842,18335},{134,1177,36,-452,22071},{513,672,-38,2023,-7209},{312,3292,76,958,6553},{405,2117,186,-345,5210},{432,4268,-304,-1091,6710},{169,3093,-393,-3600,16751},{142,1426,-45,2001,4236},{162,1906,154,3727,-13205},{466,1718,-153,1521,-16239},{271,3065,-236,2093,30947},{371,2853,-38,1716,21891},{10,1956,-46,1969,-31110},{91,2597,58,-413,36941},{169,5270,-196,1217,-20287},{60,2368,224,-3148,6855},{106,1072,123,3637,21191},{418,3921,-65,96,-30246},{383,1891,89,1279,9945},{75,4150,-58,1316,-3522},{308,3873,82,-929,16058},{196,2130,-63,-8,-22454},{406,3055,-97,4148,2462},{66,404,-12,1774,27106},{7,289,339,-1530,-10145},{23,5389,-134,-423,40004},{457,2094,-135,344,-30106},{27,1163,-83,2488,22898},{416,5253,39,-2490,4083},{499,1388,0,-3267,1636},{126,1707,-18,352,24594},{434,469,165,-241,-28645},{352,896,31,-3715,494},{172,5307,-273,1382,813},{316,4596,136,-88,27688},{135,579,-7,3907,5267},{180,3319,-154,-1899,24738},{133,5027,-148,1182,4588},{416,1181,46,996,44783},{272,605,-135,-3195,-14497},{77,1554,106,1191,-33098},{168,1316,283,1432,-10023},{250,401,-243,2583,-19656},{425,2265,40,2278,-8196},{374,4765,-274,-2369,28373},{442,2584,-186,-2554,-8936},{190,5260,276,-805,-1654},{438,1878,373,-3245,762},{180,2075,-118,93,-41464},{103,2259,222,-1824,44812},{200,312,83,95,892},{223,208,177,220,-33330},{513,585,-92,-3514,-11752},{157,1824,-191,-439,-5153},{425,1012,-42,-988,-2098},{21,3670,-240,139,-28638},{146,4321,-73,-1441,11240},{206,1747,-64,-2169,-17043},{297,1772,-173,-1549,-25755},{174,1522,65,2311,10623},{184,2616,-31,-564,-12563},{19,4609,-273,-3712,-2363},{167,1054,218,-4335,353},{42,4838,-131,-133,-13696},{473,4435,-336,-1786,2958},{440,944,101,-2328,-783},{63,210,-228,1311,-30225},{231,2701,414,433,-1484},{161,3022,-324,-3593,1988},{79,1103,-289,507,1940},{456,2024,-212,4815,-26623},{272,632,109,-496,-39440},{351,123,379,765,-35088},{206,1398,207,4247,38337},{154,81,285,3478,-3221},{88,2216,332,-1463,17452},{349,2135,-174,-3329,1514},{86,766,-280,-476,-17752},{406,118,146,1112,25424},{265,2492,-26,543,-36185},{275,4504,226,2709,-3599},{458,4277,38,223,21813},{452,1984,42,4609,24740},{79,4876,111,1288,-14102},{264,5287,54,842,-11210},{86,656,-392,-3227,-26928},{174,3972,-347,216,46903},{9,2221,-159,-2082,-62},{190,872,170,-1132,-11417},{187,3761,-136,-2287,-22581},{244,1578,61,-2477,11008},{29,1715,337,-1705,25395},{180,3677,319,2323,-32083},{369,10,189,195,-25032},{154,4661,236,-2784,23234},{285,122,108,-1161,14128},{213,1301,419,-1208,27862},{67,2588,168,-2073,-22520},{504,2815,-116,2526,-15232},{399,4840,-24,1817,1019},{31,914,190,-3449,-328},{28,779,-23,1239,-4961},{385,2778,-35,532,-5135},{269,1865,336,3,18686},{124,1289,41,-112,-4497},{21,4504,-367,3535,9880},{177,2858,-126,1857,-2027},{172,1294,332,-1390,21233},{292,4183,-95,-5321,-2897},{27,2186,-234,-2410,11878},{183,628,-248,-1351,7805},{507,902,-378,249,13757},{184,1146,287,3155,-7771},{138,1884,16,2946,-6365},{260,3032,-280,-2640,16137},{321,2888,-20,1986,10264},{476,2012,44,-173,-21983},{129,729,15,764,46996},{148,956,-54,-21,-15643},{92,4933,248,-234,-9183},{460,728,96,188,30526},{515,1803,81,-510,3894},{360,3674,-104,1471,-12140},{285,1791,109,2330,18128},{334,4971,-217,-2486,776},{468,1990,90,-367,11619},{325,717,245,-3137,43351},{135,5039,-195,-399,-28624},{135,760,-71,-1093,677},{441,3583,-126,-738,-22664},{377,1151,328,-1989,-4442},{239,1185,-46,239,2047},{31,3693,151,3580,41657},{48,3609,-273,1602,8555},{109,5523,-146,418,27026},{132,808,-76,-799,10501},{67,226,244,-469,17945},{4,3718,-15,-1384,30800},{125,1567,-96,4491,10401},{51,2815,-85,314,-16010},{129,3734,86,2857,11163},{299,1767,-103,1416,22981},{127,1309,-11,1674,-3672},{301,1553,80,2741,27715},{16,579,98,3471,-22569},{211,3001,86,-1113,-22511},{134,4371,-201,115,34978},{372,1905,-78,-3333,-2819},{243,168,-184,-2826,-4718},{505,5218,220,3337,30665},{118,5174,298,2563,27670},{434,2207,20,116,12537},{505,3307,-223,-1337,-18753},{190,4415,295,1186,15159},{508,2176,-334,622,18558},{466,1816,-18,3478,31673},{387,2896,171,1630,-4908},{491,3959,-204,779,-994},{288,4625,-8,437,-8719},{383,2143,146,-79,15995},{302,2562,53,-2882,-1692},{513,5092,43,-200,-7601},{62,3488,-39,4744,17931},{36,181,354,421,-6519},{416,3595,272,329,39462},{245,269,-245,-3221,12229},{460,5289,89,697,43898},{329,2055,33,-1148,-11772},{224,3858,113,37,18004},{222,774,489,2924,2645},{443,4836,47,2516,2655},{427,1047,124,348,-28438},{344,5288,17,831,-35309},{158,4275,2,18,-12553},{319,1994,410,-2025,-3553},{224,3659,-379,1221,-1082},{365,248,-22,702,-20987},{12,5149,39,992,27869},{484,2444,12,3336,-29940},{285,1164,-98,-754,13123},{228,3860,235,1295,-25905},{403,3954,-101,-140,-49012},{438,4262,-45,-2851,-611},{120,39,-383,430,40973},{262,21,-91,-737,-9985},{20,2203,2,3769,-10231},{169,422,-25,-179,20049},{417,2695,4,1879,-5655},{279,2581,72,-887,-13373},{98,249,-262,-98,-20321},{359,5105,-149,-1423,24114},{152,4232,-15,-3474,-17541},{368,1970,-151,-2148,23728},{85,2215,-4,-4183,-25580},{467,462,466,2510,31665},{321,3131,-135,-1197,5709},{298,2422,-119,2360,21188},{154,2301,-89,-1293,-30937},{397,4050,-65,-251,-41927},{104,286,2,2713,-33954},{238,4501,-29,1259,-39757},
            {332,4394,279,3753,-234},
            {205,3427,-439,-3609,-8019}};


}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
1205 · 对角线遍历
算法
中等
通过率
74%

题目
题解17
笔记
讨论27
排名
记录
描述
给定M×N个元素的矩阵（M行，N列），以对角线顺序返回矩阵的所有元素，如下例所示。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


给定矩阵的元素总数不会超过10,000。

样例
例1:

输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出:
[1,2,4,7,5,3,6,8,9]
例2:

输入:
[
[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]]
输出:
[1,2,5,9,6,3,4,7,10,13,14,11,8,12,15,16]
相关知识
学习《2024年9月北美大厂最新面试真题精讲》课程中的3.15Meta：最新面试精选008相关内容 ，了解更多相关知识！
标签
企业
Google
相关题目

3799
对角线遍历（二）
中等
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
242/505
已开启智能提示
发起考试
30 分 00 秒
1234567
控制台
            历史提交

 */
